#include <string>
#include <vector>

class patternMatch {
public:
	patternMatch(const string &s): pattern(s) {}
	bool patternMatchingKMP(const string &s, vector<int> &answer);
private:
	string pattern;
	void create_next(vector<int> &next);
};

bool patternMatch::patternMatchingKMP(const string &s, vector<int> &answer) {
	bool matched = false;
	vector<int> next;
	answer.clear();
	create_next(next);
	for (int i = 0, j = 0; i != s.size(); ) {
		if (j == -1 || s[i] == pattern[j]) {
			++i; ++j;
			if (j == pattern.size()) {
				matched = true; answer.push_back(i - pattern.size());
				j = next[j];
			}
		}
		else
			j = next[j];
	}
	return matched;
}

void patternMatch::create_next(vector<int> &next) {
	next.resize(pattern.size() + 1);
	next[0] = -1;
	for (int i = 0, j = -1; i != pattern.size(); ) {
		if (j == -1 || pattern[i] == pattern[j]) {
			++i; ++j;
			if (i < pattern.size() && pattern[i] == pattern[j])
				next[i] = next[j];
			else
				next[i] = j;
		}
		else
			j = next[j];
	}
}